1. Field of the Invention
The invention relates generally to the field of computer networks comprising a plurality of stations which communicate data in a ring using a token-based protocol and more specifically to a mechanism for removing data from the network.
2. Description of the Prior Art
A computer network enables various devices, such as processors, mass storage devices, and printers, to communicate with each other over high speed communication links. The devices are connected, that is, interfaced, to the network, and thus transfer data to and from the network, through stations. The stations are interconnected by the communication links.
One example of such a network is a Local Area Network (LAN). A LAN allows high-bandwidth communication among devices within a limited geographic area. The communication links are typically composed of fiber optics, coaxial cable or twisted conductor pairs.
LAN's may be configured using of a number of topologies, for example, buses or rings. In a network configured as a bus, data is communicated in either direction from the originating station. In a network configured as a ring, network stations transmit data around the ring in one direction. Thus when a station transmits data onto the ring the data travels around the ring from station to station, with each station receiving the data from the preceding station and repeating it to the succeeding station, until the data reaches the station that is to receive it. In a well-known ring network the receiving, or destination, station also repeats the data to its downstream successor and the data thus continues around the ring to the originating, or source, station.
Network stations transmit and receive data in the form of frames. The frames contain, in addition to the data, addresses, an error detection sequence and status flags, for example, a flag indicating receipt of the frame by the intended receiving, or destination, station. The frame addresses identify the source station and the destination station or stations.
Every station and every attached device are each identified by a unique address. Thus each station has associated with it its unique station-address and the addresses of its attached devices. The stations may have other addresses, for example, logical addresses, associated with them, also. A frame directed from a source station to a single destination station thus contains the address of the source station and, for example, the address of a specific device attached to the destination station. Each station may maintain a list of its associated addresses, such that the station receives the frames containing any one of its addresses.
A destination station, in addition to repeating the frame to its succeeding station, copies the frame for use by the appropriate device(s) associated with the station. The destination station may also set the applicable status flags indicating receipt of the frame.
When the frame has returned to the source station, the station, recognizing the source address in the frame as its own, removes, or strips, the frame from the ring data stream. After a transmission, the first frames received by the source station over the ring are the frames it transmitted, assuming proper operation of the stations on the ring.
The stations operate in accordance with communication protocols which facilitate the orderly transfer of the frames over the communication links. One type of communication protocol is a token-ring system. Such systems use a token, that is, a specific string of bits, to indicate that a transmitting station has completed its transmission. A succeeding station may then, following the dictates of the protocol, begin transmitting frames upon receipt of the token.
In a token-ring system a station may not transmit data over the ring unless it holds the token. Thus if a station has frames to transmit around the ring it first removes the token from the ring data stream, that is, it "captures" the token, when it receives it from the preceding station. The capturing station then begins its frame transmission. When the station is finished with the frame transmission it retransmits the token, effectively releasing it. The succeeding stations thereafter transfer the token around the ring until a station captures it in order to make a transmission.
Two or more such rings, or more generally, two or more LAN's, may be connected by a bridge, that is, a special purpose station simultaneously connected to both LAN's, to form an extended LAN. The bridge thus facilitates communication between a transmitting station on, for example, one of the rings and a receiving station on another ring. It essentially acts as the destination station on the ring containing the transmitting station and thus copies the frames directed to a second ring, while also repeating these frames on the source station ring. It also acts as a transmitting station on the second ring and transmits the copied frames in that ring after capturing the ring's token. The second ring may contain the destination station, or it may be an intermediate ring which contains a bridge to another LAN, which may, in turn, contain the destination station or be another intermediate LAN.
There are two methods of bridge operation, namely, transparent and non-transparent. A bridge operating transparently transmits the frames originated by the source station without significantly altering them, that is, without changing any portion of the frame which is protected by the frame's error detection sequence. Alternatively, a bridge operating non-transparently significantly alters the frames originated by the source station before transmitting them to the connected LAN. A non-transparent bridge may, for example, alter the source address to the address of the bridge on the second ring and/or it may alter certain other information in the frame.
The non-transparent bridge must recalculate and replace the error detection sequence contained in each of the frames to prevent the frame alterations from being treated as errors. However, if the bridge incorrectly copies a frame or inadvertently copies an erroneous frame, alters it and then recalculates the error detection sequence, it may render the frame errors undetectable. The integrity of the frame information is considered to be thus reduced.
The bridge, regardless of the mode in which it operates, must strip from the second ring the frames it transmits. Typically, a station "recognizes" the source address in that frame as its own address and strips the frame. A bridge which leaves the addresses unaltered, and which is not the original source station, may not recognize the source address in the frames it has transmitted over the second ring. The bridge is capable of transmitting frames which were originally transmitted by one of many source stations on one or more different LAN's. When the frames return to the bridge over the second ring, it may not have time to compare the frame source address with the addresses of the many source stations on the various LAN's before the decision to strip the frame must be made. Thus the bridge could repeat a frame that should be stripped by it. Accordingly, there must be a method for a bridge to determine which frames to strip.
One possible method for stripping such frames involves the bridge marking the last frame in the sequence of transmitted frames, e.g., by setting a flag in the frame. The bridge then, after a transmission, strips the frames it receives over the ring until it detects the set flag in one of the frames. If, however, the frame containing the flag is lost or corrupted, making the set flag undetectable, the bridge may continue to strip the frames it receives over the ring until it is signalled to stop, for example, by the expiration of a locally kept timer. The bridge thus strips frames originated by other stations on the extended LAN, preventing the frames from reaching their intended destinations. If the flag is a single-bit flag, a bit-error in the frame may result in the flag appearing re-set, and thus, the bridge will stop stripping before it has removed all of its frames.
A non-bridge station which connects many devices to the LAN may also have problems determining which frames it should strip. A station must determine whether to strip a frame within the time it takes the frame addresses to pass through the station. Thus the station may not have time to match the frame source address with one of its many associated addresses, and another method for determining which frames to strip must be used.